package com.yhx.leetcode.java;

import java.util.Arrays;

/**
 * @Author: mishuai
 * @Date: 2020/7/6 4:59 下午
 */
public class LeetCode16 {

    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        //和目标值最接近的三数之和
        int ans = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.length - 2; i++) {
            //如果相邻两元素相等则跳过后一个
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            //指向第二和第三个数的指针
            //第二个数的指针从左到右移动
            //第三个数的指针从右到左移动
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                //当前三数之和
                int sum = nums[i] + nums[left] + nums[right];
                // 判断当前三数之和与目标值之间的差值是否小于已找到的最小差值
                // 如果是，则更新最小差值以及最接近的三数之和
                if (Math.abs(target - sum) < Math.abs(target - ans)) {
                    ans = sum;
                }
                //如果当前三数之和等于目标值则，已找到最佳值，直接返回三数之和即可
                if (sum == target) {
                    return ans;
                } else if (sum > target) {//如果三数之和大于目标值，则应该找更小的第三个数
                    int r = right - 1;
                    while (r > left && nums[r] == nums[right]) {
                        --r;
                    }
                    right = r;
                } else {//如果三数之和小于目标值，则应该找更大的第二个数
                    int l = left + 1;
                    while (right > l && nums[l] == nums[left]) {
                        ++l;
                    }
                    left = l;
                }
            }
        }
        return ans;
    }
}
